class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        if (s.size() == 1) return 1;
        int dp[101], a = s[0] - '0', b = s[1] - '0';
        dp[0] = 1;
        dp[1] = 0;
        if (b >= 1 && b <= 9) dp[1]++;
        if (a * 10 + b >= 10 && a * 10 + b <= 26) dp[1]++;
        if (dp[1] == 0) return 0;
        for (int i = 2; i < s.size(); i++)
        {
            int m = s[i - 1] - '0', n = s[i] - '0';
            if (n >= 1 && n <= 9) dp[i] += dp[i - 1];
            if (m * 10 + n >= 10 && m * 10 + n <= 26) dp[i] += dp[i - 2];
            if (dp[i] == 0) return 0;
        }
        return dp[s.size() - 1];
    }
};